package main.leetcode.clockin.March;

/**
 * 300.最长上升子序列
 *
 * <p>给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * <p>示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 。 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 * 说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。
 *
 * <p>进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day14 {
    public static void main(String[] args) {
        System.out.println(new day14().lengthOfLIS(new int[] {1, 3, 6, 7, 9, 4, 10, 5, 6}));
    }

    // 动态规划
    //    public int lengthOfLIS(int[] nums) {
    //        int n = nums.length;
    //        if (n < 2) return n;
    //        int max, res = 0;
    //        int[] dp = new int[n]; // 记录第i个数之前的最长上升序列长度
    //        dp[0] = 1; // 初始化 1代表只有自己一个
    //        for (int i = 1; i < n; i++) {
    //            max = 0;
    //            for (int j = i - 1; j >= 0; j--) if (nums[j] < nums[i]) max = Math.max(max,
    // dp[j]);
    //            dp[i] = max + 1;
    //            res = Math.max(res, dp[i]);
    //        }
    //        return res;
    //    }

    // 贪心
    // 如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列。
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        int lo, hi, mid, end = 0; // end表示tail已填充下标
        int[] tail = new int[n]; // 记录长度为i+1的最长上升子序列的结尾数
        tail[0] = nums[0]; // 初始化，最开始长度为1的最长上升子序列结尾数为数组首元素
        for (int i = 1; i < n; i++) {
            lo = 0;
            hi = end + 1; // 因为nums[i]可能是最大数，要插入nums[end+1]的位置
            // 二分查找插入位置
            while (lo < hi) {
                mid = lo + (hi - lo) / 2;
                if (tail[mid] < nums[i]) lo = mid + 1;
                else hi = mid;
            }
            tail[lo] = nums[i];
            if (lo == end + 1) end++;
        }
        return end + 1;
    }
}
